When information is transmitted and received over a communications channel, errors sometimes occur. In order to guarantee the reliability of the message being transmitted or received, it is necessary to be able to detect these errors. Error detection is the process of determining whether information that was received is the same as the information that was sent. Once the error is detected, it may be corrected.
An example of an error that may occur in communications systems is a burst error. A burst error occurs when a number of bits in a sequence are erroneously set to the same value. FIG. 1a shows an example of a burst error in a block code 100 that contains 18 symbols 102. The burst error starts at location 6 and has a length b=3. Burst errors may be caused by erasures or random errors. Symbols that are correct are shown as empty circles, for example symbol 102. Symbols representing an error are shown as filled-in circles 104. Block code 100 has errors 104 at locations 6, 7 and 8. The remaining symbols 102, shown at locations 1-6 and 9-18, do not contain errors.
Erasure errors are the result of gaps in an information stream. For example, if information is being read from a tape and a section of the tape has been erased, an erasure error has occurred. Another example of an erasure error is when information is transmitted over a communications line that is hit by lightning during a thunderstorm. The disruption in the communications cable caused by the lightning is where the erasure error has occurred. Random errors are the result of incorrect information being transmitted. Random errors are unpredictable and need to be detected because they cause data corruption.
Existing methods for detecting errors include sending additional information along with the desired message to be transmitted. This additional information, or redundancy, is used to determine whether the message contains errors. Examples of existing error correction schemes using redundancy include cyclic redundancy checks (CRC), checksum, and Reed-Solomon codes. A Reed-Solomon code is a block code that contains a total of n symbols, and a block of k (where k&lt;n) information symbols within the block code. The k information symbols contain the message to be transmitted or received.
Assuming that k symbols make up the desired message, the remaining n-k symbols are check symbols that may be used for error correction processing. These codes are commonly indicated by the notation (n, k).
FIG. 1b shows an example of a (18, 6) Reed-Solomon code 140. Each symbol 102 is represented by a circle. Code 140 contains n=18 total symbols. The message contains k=6 symbols. The error correction portion contains n-k=12 symbols. "On TMS320 Microprocessor Base Programmable Real Time Reed-Solomon Coding-Decoding System", International Journal of Satellite Communication, Vol. 8, April 1990, written by Jing-Zheng Ouyang, discusses Reed-Solomon codes in more detail, and is hereby incorporated by reference. Also incorporated by reference is R.E. Blahut, "Theory and Practice of error Control Codes," Addison Wesley Publishing Company, Inc. 1983.
Each block code has an error correction capability, t, associated with it. T is expressed in terms of burst error length (number of symbols). This error correction capability, t, is a function of the type of error and a minimum distance, d*, corresponding to a maximum likelihood that an error may be detected. The random error correction capability of an (n, k) block code satisfies the following equation (1): EQU d*&gt;=2t+1 (1)
This equation may be expressed in terms of random errors, v, and erasure errors, r, resulting in the following equation (2): EQU d*&gt;=2v+r+1 (2)
Equation (2) reflects that random errors require a greater minimum distance for correction. In other words, the erasure correction capability is larger than the random error capability. If it can be assumed that only erasure errors, r, occurred, then equation (2) may be simplified to equation (3): EQU d*&gt;r+1 (3)
FIG. 1c shows an example of an (n, k) block code 170 having random error correction capability t=3. If more errors than t appear in a sequence, then the error for that block code cannot be corrected. For example, block code 170 contains errors 104 in positions 4, 8, 12, and 16. The burst error length is b=1 because each error 104 is not adjacent to any other error. In this case, however, even though b&lt;t, the errors may not be corrected. From a random errors point of view, the number of errors, 4, is still greater than t (t=3) and therefore no correction can be had. Also, from the point of view of burst errors, a total of 12 errors beginning from 104 at location 4 is greater than t=3 and, likewise cannot be corrected. Hence, if in the block code there were no more than t errors 104, for example as shown in FIG. 1a, where the burst error length b=3, then the error can be corrected because b=t. Similarly, block codes containing burst error length b&gt;t also could not be corrected.
Burst error length occurring in applications such as communications and data storage/retrieval presents a problem because it is unpredictable. An error correction capability t may be chosen to accommodate the longest burst error possible, i.e., the largest b value. The tradeoff is that a system that has a very high error correction capability requires more time and resources to process messages. Therefore, a need exists for maximizing the error correction capability of block codes. The present invention addresses this and related problems.